//
// Created by zhulingfeng on 2020/2/27.
//

#include <algorithm>
#include "insertion_sort.hpp"
#include "list_node.hpp"
#include "utils/utils.hpp"
int Partition(std::vector<int>& vector, int lo, int hi) {
  int v = vector[lo];
  int i = lo + 1, j = hi;
  while (true) {
    // Notice that i stops when >= v, separating element_value=v into left
    // and right sub-lists, which avoiding time complexity of QuickSort being
    // N^2 when there are large amount of duplicated values in list.
    while (i <= j && vector[i] < v) i++;
    // Notice there is no need to add j>=lo condition here, since
    // vector[lo]=v, if j=lo, the loop ends.
    while (vector[j] > v) j--;
    if (i < j) {
      swap(vector, i++, j--);
    } else {
      break;
    }
  }
  swap(vector, lo, j);
  return j;
}
void QuickSort(std::vector<int>& vector, int lo, int hi) {
  if (lo >= hi) return;
  const int kSizeThreshold = 15;
  // Use insertion sort when subarray is small.
  if (hi - lo < kSizeThreshold) {
    InsertionSort(vector, lo, hi);
    return;
  }
  int j = Partition(vector, lo, hi);
  QuickSort(vector, lo, j - 1);
  QuickSort(vector, j + 1, hi);
}
void QuickSort(std::vector<int>& vector) {
  std::random_shuffle(vector.begin(), vector.end());
  QuickSort(vector, 0, vector.size() - 1);
}
void QuickSort3Way(std::vector<int>& vector, int lo, int hi) {
  if (lo >= hi) return;
  const int kSizeThreshold = 15;
  // Use insertion sort when subarray is small.
  if (hi - lo < kSizeThreshold) {
    InsertionSort(vector, lo, hi);
    return;
  }
  int v = vector[lo];
  int lt = lo, i = lo + 1, gt = hi;
  while (i <= gt) {
    int diff = vector[i] - v;
    if (diff > 0)
      // After swap, vector[i]<=v, need to be judged again, so here i
      // does not increase.
      swap(vector, i, gt--);
    else if (diff < 0)
      // After swap, vector[i]=v.
      swap(vector, i++, lt++);
    else
      i++;
  }
  QuickSort3Way(vector, lo, lt - 1);
  QuickSort3Way(vector, gt + 1, hi);
}
void QuickSort3Way(std::vector<int>& vector) {
  std::random_shuffle(vector.begin(), vector.end());
  QuickSort3Way(vector, 0, vector.size() - 1);
}

void PartitionIntoTwoLists(ListNode* head, ListNode*& less_head,
                           ListNode*& greater_head) {
  int v = head->val;
  ListNode dummy_less(0), dummy_greater(0);
  ListNode *less_tail = &dummy_less, *greater_tail = &dummy_greater;
  head = head->next;
  // Notice the flag trick, separating element_value=v into less
  // and greater sub-lists, which avoiding time complexity of QuickSort being
  // N^2 when there are large amount of duplicated values in list.
  bool flag = false;
  while (head) {
    if (head->val < v || (flag && head->val == v)) {
      less_tail->next = head;
      less_tail = head;
      flag = !flag;
    } else {
      greater_tail->next = head;
      greater_tail = head;
      if (head->val == v) flag = !flag;
    }
    head = head->next;
  }
  // Make sure sub-lists end with nullptr, So QuickSort know when to end
  // recursion.
  less_tail->next = nullptr;
  greater_tail->next = nullptr;
  less_head = dummy_less.next;
  greater_head = dummy_greater.next;
}

ListNode* QuickSortWithTail(ListNode* head, ListNode*& tail) {
  if (!head || !head->next) {
    tail = head;
    return head;
  }
  auto equal_head = head;
  ListNode *less_head, *greater_head, *less_tail, *greater_tail;
  PartitionIntoTwoLists(head, less_head, greater_head);
  less_head = QuickSortWithTail(less_head, less_tail);
  greater_head = QuickSortWithTail(greater_head, greater_tail);
  /** Link partitioned lists and partition point **/
  if (less_head) {
    head = less_head;
    less_tail->next = equal_head;
  } else {
    head = equal_head;
  }
  equal_head->next = greater_head;
  tail = greater_tail ? greater_tail : equal_head;
  return head;
}
ListNode* QuickSortWithTail(ListNode* head) {
  ListNode* dummy;
  return QuickSortWithTail(head, dummy);
}
ListNode* QuickSort(ListNode* head) {
  if (!head || !head->next) {
    return head;
  }
  auto partition_point = head;
  ListNode *less_head, *greater_head;
  PartitionIntoTwoLists(head, less_head, greater_head);
  less_head = QuickSort(less_head);
  greater_head = QuickSort(greater_head);
  /** Link partitioned lists and partition point. **/
  if (less_head) {
    head = less_head;
    // Find less tail
    while (less_head->next) {
      less_head = less_head->next;
    }
    less_head->next = partition_point;
  } else {
    head = partition_point;
  }
  partition_point->next = greater_head;
  return head;
}

ListNode* PartitionByHeadValue(ListNode* head) {
  auto partition_point = head;
  int v = head->val;
  ListNode dummy_less(0), dummy_greater(0);
  ListNode *less_tail = &dummy_less, *greater_tail = &dummy_greater;
  head = head->next;
  // Notice the flag trick, separating element_value=v into less
  // and greater sub-lists, which avoiding time complexity of QuickSort being
  // N^2 when there are large amount of duplicated values in list.
  bool flag = false;
  while (head) {
    if (head->val < v || (flag && head->val == v)) {
      less_tail->next = head;
      less_tail = head;
      flag = !flag;
    } else {
      greater_tail->next = head;
      greater_tail = head;
      if (head->val == v) flag = !flag;
    }
    head = head->next;
  }
  less_tail->next = partition_point;
  partition_point->next = dummy_greater.next;
  greater_tail->next = nullptr;
  return dummy_less.next;
}

void Partition3Way(ListNode* head, ListNode*& less_head,
                   ListNode*& greater_head) {
  int v = head->val;
  ListNode dummy_less(0), dummy_greater(0);
  ListNode *less_tail = &dummy_less, *greater_tail = &dummy_greater;
  ListNode* equal_tail = head;
  head = head->next;
  while (head) {
    if (head->val < v) {
      less_tail->next = head;
      less_tail = head;
    } else if (head->val == v) {
      equal_tail->next = head;
      equal_tail = head;
    } else {
      greater_tail->next = head;
      greater_tail = head;
    }
    head = head->next;
  }
  // Make sure sub-lists end with nullptr, So QuickSort know when to end
  // recursion.
  less_tail->next = nullptr;
  greater_tail->next = nullptr;
  equal_tail->next = nullptr;
  less_head = dummy_less.next;
  greater_head = dummy_greater.next;
}

ListNode* QuickSort3Way(ListNode* head) {
  if (!head || !head->next) {
    return head;
  }
  auto equal_head = head;
  ListNode *less_head, *greater_head;
  Partition3Way(head, less_head, greater_head);
  less_head = QuickSort3Way(less_head);
  greater_head = QuickSort3Way(greater_head);
  /** Link partitioned lists **/
  if (less_head) {
    head = less_head;
    // Find less tail
    while (less_head->next) {
      less_head = less_head->next;
    }
    less_head->next = equal_head;
  } else {
    head = equal_head;
  }
  // Find equal_list tail
  while (equal_head->next) {
    equal_head = equal_head->next;
  }
  equal_head->next = greater_head;
  return head;
}
